/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/add-two-numbers
   @Language: C++
   @Datetime: 16-02-09 04:40
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
	/**
	 * @param l1: the first list
	 * @param l2: the second list
	 * @return: the sum list of l1 and l2 
	 * Tip : list head is small bit, list tail is big bit
	 */
	ListNode *addLists(ListNode *l1, ListNode *l2) {
		// write your code here
		int dec=10, carry=0;
		ListNode H(-1), *p;
		for(p=&H; l1 || l2 || carry;){
			carry += (l1?l1->val:0) + (l2?l2->val:0);
			p = p->next = new ListNode(carry%dec);
			carry /= dec;
			l1 = (l1?l1->next:NULL);
			l2 = (l2?l2->next:NULL);
		}
		return H.next;
	}
};
